package 算法.位运算;

public class JZ16数值的整数次方 {
    //直接运算
    public double Power(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1/ base;
            exponent = -exponent;
        }
        double res = 1.0;
        //累乘
        for(int i = 0; i < exponent; i++)
            res *= base;
        return res;
    }


    //快速幂
    //5∗5=255∗5=25(二次）、25∗25=62525∗25=625（四次）、625∗625=...625∗625=...（八次）
    /**
     *  x^n = x^n/2 * x^n/2  n为偶数
     *  x^n = x^n-1 *  x     n为奇数
     *  1                    n为0
     */
    public double Power2(double base, int exponent) {
        //处理负数次方
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        return Pow(base, exponent);
    }
    //快速幂
    private double Pow(double x, int y){
        double res = 1;
        while(y != 0){
            //可以再往上乘一个
            if((y & 1) != 0)
                res *= x;
            //叠加
            x *= x;
            //减少乘次数
            y = y >> 1;
        }
        return  res;
    }

    /**
     *  x^13 = x^8 * x^4 * x^1
     *    x^8   x^4   x^2   x^1
     *    1      1    0     1
     */
    private double myPow(double x, int n){
        double res = 1;
        while (n>0){
            if(n%2==1)
                res = res * x;
            x = x * x;
            n = n /2;
        }
        return  res;
    }

}
